package com.demo.sort;

import java.util.Arrays;

import static jdk.nashorn.internal.objects.Global.print;

/**
 * 通过一趟排序将待排序记录分割成独立的两部分，
 * 其中一部分记录的关键字均比另一部分关键字小，
 * 则分别对这两部分继续进行排序，直到整个序列有序。
 */
public class QuickSort {


    public static void main(String[] args) {
        int[] arrs = {5, 6, 3, 1, 6, 2, 7, 4, 2};
        System.out.println("排序前:" + Arrays.toString(arrs));
        qsort(arrs);
        System.out.println("排序后:" + Arrays.toString(arrs));
    }


    public static void qsort(int[] arr) {
        if (arr.length > 0) {
            sort(arr, 0, arr.length - 1);
        }
    }

    /**
     * 第归
     */
    public static void sort(int[] arr, int low, int high) {
        if (low < high) {
            //一次循环包括高位和地位排序
            int provit = povit(arr, low, high);
            sort(arr, low, provit - 1);//低位排序
            sort(arr, provit + 1, high);//高位排序
        }
    }


    /**
     * 查找中轴在arr排序后的位置 默认为最低为low
     */
    public static int povit(int[] arr, int low, int high) {
        int l = low;
        int h = high;
        int povit = arr[low];

        while (l < h) {
            while (l < h && arr[h] >= povit)
                h--;
            if (l < h) {
                int temp = arr[h];
                arr[h] = arr[l];
                arr[l] = temp;
                l++;
            }

            while (l < h && arr[l] <= povit)
                l++;

            if (l < h) {
                int temp = arr[h];
                arr[h] = arr[l];
                arr[l] = temp;
                h--;
            }
        }
        return povit;
    }

    public static void ss(int arr[], int low, int high) {
        int l = low;
        int h = high;
        int povit = arr[low];

        while (l < h) {
            while (l < h && arr[h] >= povit)
                h--;
            if (l < h) {
                int temp = arr[h];
                arr[h] = arr[l];
                arr[l] = temp;
                l++;
            }

            while (l < h && arr[l] <= povit)
                l++;

            if (l < h) {
                int temp = arr[h];
                arr[h] = arr[l];
                arr[l] = temp;
                h--;
            }
        }
        print(arr);
        System.out.print("l=" + (l + 1) + "h=" + (h + 1) + "povit=" + povit + "\n");
        if (l > low) sort(arr, low, l - 1);
        if (h < high) sort(arr, l + 1, high);
    }


}
